import math
from collections import Counter

# 计算两个数据点的欧几里得距离
def euclidean_distance(x1, x2):
    return math.sqrt(sum((a - b) ** 2 for a, b in zip(x1, x2)))

# KNN算法
def KNN(train_data, test_point, k):
    # 1. 计算测试点和每个训练样本的距离
    distances = []
    for data_point, label in train_data:
        dist = euclidean_distance(test_point, data_point)
        distances.append((dist, label))
    
    # 2. 按照距离升序排序
    distances.sort(key=lambda x: x[0])
    
    # 3. 选取前K个邻居
    k_nearest_neighbors = distances[:k]
    
    # 4. 投票机制（选择出现次数最多的类别）
    labels = [label for _, label in k_nearest_neighbors]
    most_common_label = Counter(labels).most_common(1)[0][0]
    
    return most_common_label

# 示例数据
train_data = [
    ([1.0, 2.0], 'A'),
    ([1.5, 1.8], 'A'),
    ([5.0, 8.0], 'B'),
    ([8.0, 8.0], 'B'),
    ([1.0, 0.6], 'A'),
    ([9.0, 11.0], 'B'),
    ([8.0, 2.0], 'A'),
    ([10.0, 2.0], 'B'),
    ([9.0, 3.0], 'B')
]

test_point = [7.0, 3.0]
k = 3

# 使用KNN算法进行分类
predicted_label = KNN(train_data, test_point, k)
print(f"测试点 {test_point} 的预测类别是: {predicted_label}")
